package com.algorithm;

/**
 * @author: sun.hongliang
 * @create: 2019/12/06 10:56
 */
public class LongestSubstringTest {
    public static void main(String[] args) {

    }

    public int longestSubstring(String s, int k) {
        if (s.length() < k) {
            return 0;
        }
        if (k < 2) {
            return s.length();
        }
        return count(s.toCharArray(), k, 0, s.length() - 1);
    }

    private int count(char[] chars, int k, int p, int q) {
        if (q - p + 1 < k)
            return 0;
        int[] times = new int[26];
        for (int i = p; i <= q; i++) {
            int c = chars[i] - 'a';
            times[c] = times[c] + 1;
        }
        while (q - p + 1 >= k && times[chars[p] - 'a'] < k) {
            p++;
        }

        while (q - p + 1 >= k && times[chars[q] - 'a'] < k) {
            q--;
        }
        if (q - p + 1 < k)
            return 0;

        for (int i = p; i <= q; i++) {
            int c = chars[i] - 'a';
            if (times[c] < k) {
                return Math.max(count(chars, k, p, i - 1), count(chars, k, i + 1, q));
            }
        }

        return q - p + 1;
    }
}
